package personal.leil.learning.radix;

import personal.leil.learning.utils.ArrayUtils;

/**
 * 基数排序（桶排序）
 * <p>
 * 基数排序代码实现
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024-1-12
 */
public class RadixSort {

    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1);
    }

    /**
     * 基数排序
     * <p>
     * 基数排序代码实现
     * </p>
     *
     * @param arr source array
     * @param L   bound of left for sorting
     * @param R   bound of right for sorting
     */
    public static void radixSort(int[] arr, int L, int R) {
        int[] help = new int[R - L + 1];
        /*
         * @param digit 最大数的十进制位的个数（eg. 10=>1  100=>2  1000=>3)
         */
        int digit = maxbits(arr, L, R);
        for (int i = 1; i <= digit; i++) {
            int[] bucket = new int[10];
            // count for digit in arr
            for (int j = L; j <= R; j++) {
                int num = getNumForDigit(arr[j], i);
                bucket[num]++;
            }
            // calculate position for sorted
            for (int j = 1; j < bucket.length; j++) {
                bucket[j] += bucket[j - 1];
            }
            // 出桶
            for (int j = R; j >= L; j--) {
                int num = getNumForDigit(arr[j], i);
                int count = bucket[num];
                // count为出现的次数，体现在数组的索引上要-1
                help[count - 1] = arr[j];
                bucket[num]--;
            }
            // copy to source array
            for (int j = 0; j < help.length; j++) {
                arr[L + j] = help[j];
            }
        }
    }

    /**
     * 获取数组arr上L到R区间上最大数字位数
     *
     * @param arr source array
     * @param L   bound of left for calculate
     * @param R   bound of right for calculate
     * @return digit for max number
     */
    private static int maxbits(int[] arr, int L, int R) {
        // find max
        int max = Integer.MIN_VALUE;
        for (int i = L; i <= R; i++) {
            max = Math.max(max, arr[i]);
        }
        int digit = 0;
        while (max != 0) {
            digit++;
            max /= 10;
        }
        return digit;
    }


    /**
     * 获取某个数字对应10进制位上的数
     *
     * @param num   target number
     * @param digit target digit
     * @return number for result
     */
    private static int getNumForDigit(int num, int digit) {
        int multiple = (int) Math.pow(10, digit);
        return (num / multiple) % 10;
    }


    /********************* For Test *************************/

    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArr(10);
        System.out.println("before sort:");
        ArrayUtils.printArr(arr);
        radixSort(arr);
        System.out.println("after sort:");
        ArrayUtils.printArr(arr);
    }

}
